{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of K Consecutive Bit Flips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #queue #array #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #队列 #数组 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minKBitFlips"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 连续位的最小翻转次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二进制数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p><strong>k位翻转</strong> 就是从 <code>nums</code> 中选择一个长度为 <code>k</code> 的 <strong>子数组</strong> ，同时把子数组中的每一个 <code>0</code> 都改成 <code>1</code> ，把子数组中的每一个 <code>1</code> 都改成 <code>0</code> 。</p>\n",
    "\n",
    "<p>返回数组中不存在 <code>0</code> 所需的最小 <strong>k位翻转</strong> 次数。如果不可能，则返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组的 <strong>连续</strong> 部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,1,0], K = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>先翻转 A[0]，然后翻转 A[2]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,0], K = 2\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,0,0,1,0,1,1,0], K = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "翻转 A[0],A[1],A[2]:&nbsp;A变成 [1,1,1,1,0,1,1,0]\n",
    "翻转 A[4],A[5],A[6]:&nbsp;A变成 [1,1,1,1,1,0,0,0]\n",
    "翻转 A[5],A[6],A[7]:&nbsp;A变成 [1,1,1,1,1,1,1,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-k-consecutive-bit-flips](https://leetcode.cn/problems/minimum-number-of-k-consecutive-bit-flips/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-k-consecutive-bit-flips](https://leetcode.cn/problems/minimum-number-of-k-consecutive-bit-flips/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,0]\\n1', '[1,1,0]\\n2', '[0,0,0,1,0,1,1,0]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            # 表示之前翻转过\n",
    "            if i - k >= 0 and nums[i-k] > 1:\n",
    "                cnt ^= 1\n",
    "                nums[i - k] -= 2\n",
    "            # 需要翻转\n",
    "            if (cnt + num) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                nums[i] += 2\n",
    "                cnt ^= 1\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        res = cnt = 0\n",
    "        for i in range(n):\n",
    "            cnt += diff[i]\n",
    "            if (nums[i] + cnt) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return - 1\n",
    "                diff[i + 1] += 1\n",
    "                diff[i + k] -= 1\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        ans, cnt = 0, 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            cnt += diff[i]\n",
    "            # 需要翻转\n",
    "            if (num + cnt) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                diff[i + 1] += 1\n",
    "                diff[i + k] -= 1\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        if nums[0] == 0:\n",
    "            ans += 1\n",
    "            for i in range(k):\n",
    "                nums[i] ^= 1\n",
    "\n",
    "        diff = [False] * (len(nums) - 1)\n",
    "        for i in range(len(nums) - 1):\n",
    "            diff[i] = (nums[i] != nums[i + 1])\n",
    "\n",
    "        for i in range(len(diff) - k + 1):\n",
    "            if diff[i]:\n",
    "                ans += 1\n",
    "                diff[i] = not diff[i]\n",
    "                if i + k < len(diff):\n",
    "                    diff[i + k] = not diff[i + k]\n",
    "        \n",
    "        if sum(diff) == 0:\n",
    "            return ans\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "    #     n = len(nums)\n",
    "    #     diff = [0] * (n + 1)\n",
    "    #     rev_cnt = 0\n",
    "    #     ans = 0\n",
    "    #     for i in range(n):\n",
    "    #         rev_cnt += diff[i]\n",
    "    #         if (nums[i] + rev_cnt) & 1 == 0:\n",
    "    #             if i + k > n:\n",
    "    #                 return -1\n",
    "    #             rev_cnt += 1\n",
    "    #             diff[i + k] -= 1\n",
    "    #             ans += 1\n",
    "    #     return ans\n",
    "\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        rev = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            rev ^= diff[i]\n",
    "            if nums[i] == rev:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                rev ^= 1\n",
    "                diff[i + k] ^= 1\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * n\n",
    "        ans = pre = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            pre += diff[i]\n",
    "            if pre % 2 == nums[i]:\n",
    "                if i + k - 1 >= n:\n",
    "                    return -1\n",
    "                ans += 1\n",
    "                pre += 1\n",
    "                if i+k < n:\n",
    "                    diff[i+k] -= 1\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0]*(n + 1) # 差分数组记录反转次数\n",
    "        pre_s = 0 # 前缀和\n",
    "        ans = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            pre_s += diff[i] # 前缀和代表当前元素的翻转次数\n",
    "            if (x + pre_s) & 1 == 0: # 当前x为0,需要翻转[i，i+k]\n",
    "                diff[i] += 1\n",
    "                pre_s += 1\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                diff[i + k] -= 1\n",
    "                ans += 1 # 此处翻转一次\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        arr = [0] * (len(nums)+1)\n",
    "        for i in range(0, len(nums)):\n",
    "            count += arr[i]\n",
    "            if count % 2 == 1: # reversee\n",
    "                if nums[i] == 1:\n",
    "                    ans += 1\n",
    "                    count += 1\n",
    "                    arr[i] += 1\n",
    "                    if i+k <= len(nums):\n",
    "                        arr[i+k] -= 1\n",
    "                    else:\n",
    "                        return -1\n",
    "            else:\n",
    "                if nums[i] == 0:\n",
    "                    ans += 1\n",
    "                    count += 1\n",
    "                    arr[i] += 1\n",
    "                    if i+k <= len(nums):\n",
    "                        arr[i+k] -= 1\n",
    "                    else:\n",
    "                        return -1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        rev_cnt = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            rev_cnt += diff[i]\n",
    "            if (nums[i] + rev_cnt) & 1 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                rev_cnt += 1\n",
    "                diff[i + k] -= 1\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            # 表示i-k翻转过\n",
    "            if i >= k and nums[i-k] > 1:\n",
    "                cnt ^= 1\n",
    "                nums[i - k] -= 2\n",
    "            # 根据值的情况决定是否翻转\n",
    "            # 需要翻转的情况\n",
    "            if num == cnt:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                ans += 1\n",
    "                cnt ^= 1\n",
    "                nums[i] += 2\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        flip_count = 0\n",
    "        flip_needed = [0] * n\n",
    "        curr_flip = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if i >= k:\n",
    "                curr_flip ^= flip_needed[i - k]\n",
    "\n",
    "            if (nums[i] + curr_flip) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                flip_needed[i] = 1\n",
    "                curr_flip ^= 1\n",
    "                flip_count += 1\n",
    "\n",
    "        return flip_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            cnt += diff[i]\n",
    "            # 需要翻转\n",
    "            if (num + cnt) % 2 == 0:\n",
    "                if (i + k) > n:\n",
    "                    return -1\n",
    "                diff[i + 1] += 1\n",
    "                diff[i + k] -= 1\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        diff = [0] * (len(nums) + 1)\n",
    "        res = 0\n",
    "        revCnt = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            revCnt += diff[i]\n",
    "\n",
    "            if (n + revCnt) % 2 == 0:\n",
    "                diff[i] += 1\n",
    "                if i + k >= len(diff):\n",
    "                    return -1\n",
    "                diff[i + k] -= 1\n",
    "\n",
    "                revCnt += 1\n",
    "                res += 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        # 滑动窗口\n",
    "        n = len(nums)\n",
    "        flip_count = 0\n",
    "        pos = 0\n",
    "        ans = 0\n",
    "\n",
    "        while pos < n:\n",
    "            if pos - k >= 0 and nums[pos-k] == 2:\n",
    "                flip_count -= 1\n",
    "            if (flip_count + nums[pos]) % 2 == 0:\n",
    "                if pos + k > n:\n",
    "                    return -1\n",
    "                nums[pos] = 2\n",
    "                flip_count += 1\n",
    "                ans += 1\n",
    "            pos += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        # 差分数组\n",
    "        # 翻转次数的差分数组的前缀和就是到这个元素时翻转过的次数，之后怎么样是不知道的。所以，A[i]+revCnt如果是偶数，要么偶数+偶数=偶数，或者奇数+奇数=偶数。如果是前者，原来是0，翻转偶数次后还是0，所以还需要翻转一次；如果是后者，原来是1，翻转奇数次后变成0，也需要再翻转一次。\n",
    "\n",
    "        n = len(nums)\n",
    "        d = [0] *n # d[i] = reA[i]  = reA[i-1]  d[0] = 0, reA 表示每一位翻转次数的数组\n",
    "        ans = 0\n",
    "        sumReA = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            sumReA += d[i]\n",
    "            if (sumReA + nums[i]) % 2 == 0: #需要再次翻转\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                # [i:i+k] 翻转 \n",
    "                d[i] += 1\n",
    "                if i + k < n:\n",
    "                    d[i + k] -= 1\n",
    "                sumReA += 1 # 由d[i] += 1 引起\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        diff = [0] * (len(nums) + 1)\n",
    "        cnt = 0\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            if (nums[i] + cnt) % 2 == 0:\n",
    "                res += 1\n",
    "                if i + k - 1 >= len(nums):\n",
    "                    return -1\n",
    "                diff[i] += 1\n",
    "                diff[i + k - 1] -= 1\n",
    "            cnt += diff[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        diff = [0]*len(nums)\n",
    "        cur = 0\n",
    "        for i in range(len(nums)-k+1):\n",
    "            cur += diff[i]\n",
    "            if (nums[i] == 0 and cur%2==0) or (nums[i]==1 and cur%2==1):\n",
    "                diff[i] += 1\n",
    "                if i+k<len(nums):\n",
    "                    diff[i+k] -= 1\n",
    "                nums[i] = 1\n",
    "                count += 1\n",
    "                cur += 1\n",
    "        for i in range(len(nums)-k+1, len(nums)):\n",
    "            cur += diff[i]\n",
    "            if (nums[i] == 0 and cur%2==0) or (nums[i]==1 and cur%2==1):\n",
    "                return -1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        len1 = len(nums)\n",
    "        count, pre = [0] * len1, 0\n",
    "        for i in range(len(nums)):\n",
    "            if i >= k:\n",
    "                pre ^= count[i - k]\n",
    "\n",
    "            if nums[i] != pre:\n",
    "                count[i] = 0\n",
    "            else:\n",
    "                if i > len1 - k:\n",
    "                    return -1\n",
    "                count[i] = 1\n",
    "            pre ^= count[i]\n",
    "        return sum(count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        ans, cnt = 0, 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            cnt += diff[i]\n",
    "            # 需要翻转\n",
    "            if (num + cnt) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                diff[i + 1] += 1\n",
    "                diff[i + k] -= 1\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        len1 = len(nums)\n",
    "        count, pre = [0] * len1, 0\n",
    "        for i in range(len(nums)):\n",
    "            if i >= k:\n",
    "                pre ^= count[i - k]\n",
    "\n",
    "            if nums[i] != pre:\n",
    "                count[i] = 0\n",
    "            else:\n",
    "                if i > len1 - k:\n",
    "                    return -1\n",
    "                count[i] = 1\n",
    "            pre ^= count[i]\n",
    "        return sum(count)\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.minKBitFlips([0,0,0,1,0,1,1,0], 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if i >= k and nums[i - k] >1:\n",
    "                cnt ^= 1\n",
    "                nums[i - k] -= 2\n",
    "            if (num + cnt) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                cnt ^= 1\n",
    "                nums[i] += 2\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            s += diff[i]\n",
    "            if (s + x) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                ans += 1\n",
    "                s += 1\n",
    "                diff[i] += 1\n",
    "                diff[i + k] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        filp_count = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i - k >= 0 and nums[i - k] == 2:\n",
    "                filp_count -= 1\n",
    "            if (filp_count + nums[i]) % 2 == 0:\n",
    "                if i + k > len(nums):\n",
    "                    return -1\n",
    "                nums[i] = 2\n",
    "                filp_count += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        diff = [0]*len(nums)\n",
    "        cur = 0\n",
    "        for i in range(len(nums)-k+1):\n",
    "            cur += diff[i]\n",
    "            if (nums[i] == 0 and cur%2==0) or (nums[i]==1 and cur%2==1):\n",
    "                diff[i] += 1\n",
    "                if i+k<len(nums):\n",
    "                    diff[i+k] -= 1\n",
    "                nums[i] = 1\n",
    "                count += 1\n",
    "                cur += 1\n",
    "        for i in range(len(nums)-k+1, len(nums)):\n",
    "            cur += diff[i]\n",
    "            if (nums[i] == 0 and cur%2==0) or (nums[i]==1 and cur%2==1):\n",
    "                return -1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        revCnt = 0\n",
    "        for i in range(n):\n",
    "            revCnt -= int(nums[i] / 2)\n",
    "            if (nums[i] + revCnt) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                revCnt += 1\n",
    "                if i+k < n:\n",
    "                    nums[i+k] += 2\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        output = 0\n",
    "        ans = 0\n",
    "        for i in range(0, n):\n",
    "            ans += diff[i]\n",
    "            if (ans + nums[i]) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                ans += 1\n",
    "                output += 1\n",
    "                diff[i + k] -= 1\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        d = [0] * (n + 1)\r\n",
    "        res = 0\r\n",
    "        s = 0\r\n",
    "        for i in range(len(nums) - k + 1):\r\n",
    "            s += d[i]\r\n",
    "            if s & 1 == nums[i]:\r\n",
    "                res += 1\r\n",
    "                s += 1 \r\n",
    "                d[i + k] -= 1\r\n",
    "        for j in range(len(nums) - k + 1, len(nums)):\r\n",
    "            s += d[j]\r\n",
    "            if s & 1 == nums[j]:\r\n",
    "                return -1\r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, A: List[int], K: int) -> int:\n",
    "        n = len(A)\n",
    "        f = [0] * (n + 1)\n",
    "        ans, flip = 0, 0\n",
    "        for i in range(n):\n",
    "            flip += f[i]\n",
    "            if (A[i] + flip) % 2 == 0: #需要翻转\n",
    "                if i + K > n: #出界了，就结束\n",
    "                    return -1\n",
    "                ans += 1 # 翻转次数\n",
    "                flip += 1 # 左侧位置+1 直接传递到 revCnt 上\n",
    "                f[i + K] -= 1 # 右端点+1 位置 -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, A: List[int], K: int) -> int:\n",
    "        n = len(A)\n",
    "        f = [0] * (n + 1)\n",
    "        ans, flip = 0, 0\n",
    "        for i in range(n):\n",
    "            flip += f[i]\n",
    "            if (A[i] + flip) % 2 == 0: #需要翻转\n",
    "                if i + K > n: #出界了，就结束\n",
    "                    return -1\n",
    "                f[i] += 1\n",
    "                ans += 1 # 翻转次数\n",
    "                flip += 1 # 左侧位置+1 直接传递到 revCnt 上\n",
    "                f[i + K] -= 1 # 右端点+1 位置 -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        queue = collections.deque()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if queue and i >= queue[0] + k: # 维持最小翻转次数k\n",
    "                queue.popleft()\n",
    "            if len(queue) % 2 == nums[i]:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                queue.append(i)\n",
    "                ans += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = collections.deque()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if q and i >= q[0] + k:\n",
    "                q.popleft()\n",
    "            if len(q) % 2 == nums[i]:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                q.append(i)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, s: List[int], k: int) -> int:\n",
    "        q =  collections.deque()\n",
    "        ans = 0\n",
    "\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if q and i >= q[0] + k:\n",
    "                q.popleft()\n",
    "            if len(q) % 2 == s[i]:\n",
    "                if i + k > n :\n",
    "                    return - 1\n",
    "                q.append(i)\n",
    "                \n",
    "\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        dq = deque()\n",
    "        for i, x in enumerate(nums):\n",
    "            if dq and i >= dq[0] + k:  # 作用域检查\n",
    "                dq.popleft()\n",
    "            if len(dq) % 2 == x:  # 是1，前面翻转奇数次；或者是0， 前面翻转偶数次。那么i需要进行翻转\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                ans += 1\n",
    "                dq.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, s: List[int], k: int) -> int:\n",
    "        q = []\n",
    "        ans = 0\n",
    "\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if q and i >= q[0] + k:\n",
    "                q.pop(0)\n",
    "            if len(q) % 2 == s[i]:\n",
    "                if i + k > n :\n",
    "                    return - 1\n",
    "                q.append(i)\n",
    "                \n",
    "\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "        que = collections.deque()\n",
    "        res = 0;\n",
    "        for i in range(N):\n",
    "            while que and i >= que[0] + k:\n",
    "                que.popleft()\n",
    "            if len(que)%2 == nums[i]:\n",
    "                if i+k > N: return -1\n",
    "                que.append(i)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if k > n:\n",
    "            return -1\n",
    "        queue = []\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if queue and queue[0] + k == i:\n",
    "                queue.pop(0)\n",
    "            if (len(queue) + nums[i]) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                queue.append(i)\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "        que = collections.deque()\n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            if que and i >= que[0] + k:\n",
    "                que.popleft()\n",
    "            if len(que) % 2 == nums[i]:\n",
    "                if i + k > N: return -1\n",
    "                que.append(i)\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minKBitFlips(self, A, K):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        N = len(A)\n",
    "        que = collections.deque()\n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            if que and i >= que[0] + K:\n",
    "                que.popleft()\n",
    "            if len(que) % 2 == A[i]:\n",
    "                if i +  K > N: return -1\n",
    "                que.append(i)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        dq = deque()  # 记录翻转的起点\n",
    "        for i, x in enumerate(nums):\n",
    "            while dq and dq[0] + k - 1 < i:\n",
    "                dq.popleft()\n",
    "            if (len(dq) & 1) ^ x:  # len(dq) & 1 表示 x 翻转的次数的奇偶性\n",
    "                continue\n",
    "            if i > n - k:\n",
    "                return -1\n",
    "            dq.append(i)\n",
    "            ans += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        res = 0\r\n",
    "        rev = 0\r\n",
    "        end: deque[int] = deque()\r\n",
    "\r\n",
    "        for i in range(n):\r\n",
    "            if end and i == end[0]:\r\n",
    "                rev ^= 1\r\n",
    "                end.popleft()\r\n",
    "\r\n",
    "            if nums[i] ^ rev != 1:\r\n",
    "                if i + k > n: return -1\r\n",
    "                end.append(i + k)\r\n",
    "                res += 1\r\n",
    "                rev ^= 1\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        # N = len(nums)\n",
    "        # res = 0\n",
    "        # for i in range(N - K + 1):\n",
    "        #     if nums[i] == 1:\n",
    "        #         continue\n",
    "        #     for j in range(K):\n",
    "        #         nums[i + j] ^= 1\n",
    "        #     res += 1\n",
    "        # for i in range(N):\n",
    "        #     if nums[i] == 0:\n",
    "        #         return -1\n",
    "        # return res\n",
    "        n = len(nums)\n",
    "        q = deque()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if q and q[0] + k <= i:\n",
    "                q.popleft()\n",
    "            if len(q) % 2 == nums[i]:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                q.append(i)\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        # 贪心 + 优化 = 滑动窗口\n",
    "        q = deque()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if q and i >= q[0]+k:\n",
    "                q.popleft()\n",
    "            if len(q)%2 == nums[i]:\n",
    "                # 细节\n",
    "                if i + k > n:return -1\n",
    "                ans += 1\n",
    "                q.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        length = len(nums)\n",
    "        queue = collections.deque()\n",
    "        result = 0\n",
    "        for i in range(length):\n",
    "            if queue and queue[0] <= i - k:\n",
    "                queue.popleft()\n",
    "            if len(queue) % 2 == nums[i]:\n",
    "                if i + k > length:\n",
    "                    return -1\n",
    "                queue.append(i)\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = collections.deque()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if q and i >= q[0] + k:\n",
    "                q.popleft()\n",
    "            if len(q) % 2 == nums[i]:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                q.append(i)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if k > n:\n",
    "            return -1\n",
    "        queue = deque()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if queue and queue[0] + k == i:\n",
    "                queue.popleft()\n",
    "            if (len(queue) + nums[i]) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                queue.append(i)\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        # 贪心 + 优化 = 滑动窗口\n",
    "        q = deque()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if q and i >= q[0]+k:\n",
    "                q.popleft()\n",
    "            if len(q)%2 == nums[i]:\n",
    "                if i + k > n:return -1\n",
    "                ans += 1\n",
    "                q.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    # Moving window. Time O(n) Space O(k)\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        # window: maintains the starting indices of flipped windows, in previou k elements\n",
    "        window = deque()\n",
    "        for i in range(n):\n",
    "            # expel the first element, if i is outside of it's influence\n",
    "            if window and window[0] + k <= i:\n",
    "                window.popleft()\n",
    "            # if i can be flipped AND needs to be flipped, add to window\n",
    "            if len(window) % 2 == nums[i]:\n",
    "                # if i actually cannot be flipped, return -1\n",
    "                if i > n - k: return -1\n",
    "                window.append(i)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        # 模拟翻转\n",
    "        res = 0\n",
    "        size = len(nums)\n",
    "        que = collections.deque()\n",
    "        for i in range(size):\n",
    "            if que and i >= (que[0] + k):\n",
    "                que.popleft()\n",
    "\n",
    "            if len(que) % 2 == nums[i]:\n",
    "                if i + k > size: return -1\n",
    "                que.append(i)\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        que = collections.deque()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if que and i >= que[0] + k:\n",
    "                que.popleft()\n",
    "            if (len(que) + nums[i]) % 2 == 0:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                que.append(i)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "    #     n = len(nums)\n",
    "    #     diff = [0] * (n + 1)\n",
    "    #     rev_cnt = 0\n",
    "    #     ans = 0\n",
    "    #     for i in range(n):\n",
    "    #         rev_cnt += diff[i]\n",
    "    #         if (nums[i] + rev_cnt) & 1 == 0:\n",
    "    #             if i + k > n:\n",
    "    #                 return -1\n",
    "    #             rev_cnt += 1\n",
    "    #             diff[i + k] -= 1\n",
    "    #             ans += 1\n",
    "    #     return ans\n",
    "\n",
    "    # def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "    #     n = len(nums)\n",
    "    #     diff = [0] * (n + 1)\n",
    "    #     rev = 0\n",
    "    #     ans = 0\n",
    "    #     for i in range(n):\n",
    "    #         rev ^= diff[i]\n",
    "    #         if nums[i] == rev:\n",
    "    #             if i + k > n:\n",
    "    #                 return -1\n",
    "    #             rev ^= 1\n",
    "    #             diff[i + k] ^= 1\n",
    "    #             ans += 1\n",
    "    #     return ans\n",
    "\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = deque()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            while q and q[0] + k <= i:\n",
    "                q.popleft()\n",
    "            if nums[i] == len(q) & 1:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                q.append(i)\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minKBitFlips(self, A, K):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        N = len(A)\n",
    "        que = collections.deque()\n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            if que and i >= que[0] + K:\n",
    "                que.popleft()\n",
    "            if len(que) % 2 == A[i]:\n",
    "                if i +  K > N: return -1\n",
    "                que.append(i)\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        # 核心思想：贪心，遇到0就翻转，因为前面翻转0，并不影响后面0得到翻转\n",
    "        q = deque([])\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if q and i >= q[0] + k:\n",
    "                q.popleft()\n",
    "            if len(q)%2 == nums[i]:\n",
    "                # 表示长度已经不够k了\n",
    "                if i+k > n:return -1\n",
    "                ans += 1\n",
    "                q.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        que = collections.deque()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if que and i >= que[0] + k:\n",
    "                que.popleft()\n",
    "            if len(que) % 2 == nums[i]:\n",
    "                if i + k > n:\n",
    "                    return -1\n",
    "                que.append(i)\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKBitFlips(self, nums: List[int], k: int) -> int:\n",
    "        queue = collections.deque([])\n",
    "        res = 0\n",
    "\n",
    "        # i, i - 1, i - k + 1\n",
    "        for i in range(len(nums)):\n",
    "            while queue and queue[0] < i - k + 1:\n",
    "                queue.popleft()\n",
    "\n",
    "            if (nums[i] + len(queue)) % 2 == 0:\n",
    "                if i + k - 1 >= len(nums):\n",
    "                    return -1\n",
    "                res += 1\n",
    "                queue.append(i)\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
